//
//  41.和为S的连续正数序列.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/27.
//

import Foundation
/*
 题目：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 思路1：前缀和O(n^2), 因为至少两个数相加，外层只需遍历小于中位数的值
 思路2：窗口扫描
 */
func offer_41() {
    print(Solution().findContinuousSequence2(9))
}

fileprivate class Solution {
    func findContinuousSequence1(_ sum: Int) -> [[Int]] {
        guard sum > 1 else { return [] }
        var result = [[Int]]()
        for i in 1...sum/2 {
            var s = 0
            var tempArr = [Int]()
            for j in i..<sum {
                s += j
                tempArr.append(j)
                if s == sum {
                    result.append(tempArr)
                    break
                } else if s > sum {
                    break
                }
            }
        }
        return result
    }
    
    func findContinuousSequence2(_ sum: Int) -> [[Int]] {
        guard sum > 1 else { return [] }
        var result = [[Int]]()
        var left = 1
        var right = 1
        var s = 0
        while left <= sum/2 {
            if s < sum {
                s += right
                right += 1
            } else if s > sum {
                s -= left
                left += 1
            } else {
                result.append(Array(left..<right))
                s -= left
                left += 1
            }
        }
        return result
    }
}


